package club.xiaojiawei.dp;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/9/22 2:19 PM
 * @question 647. 回文子串
 * @description 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
 */
public class CountSubstrings647 {

    public static void main(String[] args) {
        CountSubstrings647 test = new CountSubstrings647();
        int result = test.countSubstrings4("abcdefg");
        System.out.println(result);
    }

    /**
     * 双指针
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if (s.length() < 2){
            return s.length();
        }
        int left = 0, right = 1, count = 0, amount, length = s.length();
        char[] chars = s.toCharArray();
        while (right < length){
            amount = 0;
            while (left >= 0 && right < length && chars[left] == chars[right]){
                amount++;
                left--;
                right++;
            }
            if (amount == 0){
                right++;
                left++;
            }else {
                count += amount;
                right = right - amount + 1;
                left = right - 1;
            }
        }
        if (length > 2){
            left = 0;
            right = 2;
            while (right < length){
                amount = 0;
                while (left >= 0 && right < length && chars[left] == chars[right]){
                    amount++;
                    left--;
                    right++;
                }
                if (amount == 0){
                    right++;
                    left++;
                }else {
                    count += amount;
                    right = right - amount + 1;
                    left = right - 2;
                }
            }
        }
        return count + length;
    }

    /**
     * 双指针-优化
     * @param s
     * @return
     */
    public int countSubstrings2(String s) {
        if (s.length() < 2){
            return s.length();
        }
        int left = 0, right = 1, count = 0, amount, length = s.length();
        char[] chars = s.toCharArray();
        while (right < length){
            amount = 0;
            while (left >= 0 && right < length && chars[left] == chars[right]){
                amount++;
                left--;
                right++;
            }
            if (amount == 0){
                if (right - left == 1){
                    right++;
                }else {
                    left++;
                }
            }else {
                count += amount;
                if (right - left - 1 == amount << 1){
                    right -= amount - 1;
                    left = right - 2;
                }else {
                    right -= amount;
                    left = right - 1;
                }
            }
        }
        return count + length;
    }

    /**
     * 官方-中心扩展
     * 时间复杂度：O(n^2)
     * 空间复杂度：O(1)
     * @param s
     * @return
     */
    public int countSubstrings3(String s) {
        int n = s.length(), ans = 0;
        for (int i = 0; i < 2 * n - 1; ++i) {
            int l = i / 2, r = i / 2 + i % 2;
            while (l >= 0 && r < n && s.charAt(l) == s.charAt(r)) {
                --l;
                ++r;
                ++ans;
            }
        }
        return ans;
    }

    /**
     * 官方-Manacher算法
     * 时间复杂度：O(n)
     * 空间复杂度：O(n)
     * @param s
     * @return
     */
    public int countSubstrings4(String s) {
        int n = s.length();
//        这里的$和下面的!都是为了防止数组越界而设置的
        StringBuilder t = new StringBuilder("$#");
        for (int i = 0; i < n; ++i) {
            t.append(s.charAt(i));
            t.append('#');
        }
        n = t.length();
        t.append('!');
        int[] f = new int[n];
        int iMax = 0, rMax = 0, ans = 0;
        for (int i = 1; i < n; ++i) {
            // 初始化 f[i]
            f[i] = i <= rMax ? Math.min(rMax - i + 1, f[2 * iMax - i]) : 1;
            // 中心拓展
            while (t.charAt(i + f[i]) == t.charAt(i - f[i])) {
                ++f[i];
            }
            // 动态维护 iMax 和 rMax
            if (i + f[i] - 1 > rMax) {
                iMax = i;
                rMax = i + f[i] - 1;
            }
            // 统计答案, 当前贡献为 (f[i] - 1) / 2 上取整
            ans += f[i] / 2;
        }
        return ans;
    }

    /**
     * 官方-dp
     * @param s
     * @return
     */
    public int countSubstrings5(String s) {
        int len, ans = 0;
        if (s == null || (len = s.length()) < 1) return 0;
        //dp[i][j]：s字符串下标i到下标j的字串是否是一个回文串，即s[i, j]
        boolean[][] dp = new boolean[len][len];
        for (int j = 0; j < len; j++) {
            for (int i = 0; i <= j; i++) {
                //当两端字母一样时，才可以两端收缩进一步判断
                if (s.charAt(i) == s.charAt(j)) {
                    //i++，j--，即两端收缩之后i,j指针指向同一个字符或者i超过j了,必然是一个回文串
                    if (j - i < 3) {
                        dp[i][j] = true;
                    } else {
                        //否则通过收缩之后的字串判断
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {//两端字符不一样，不是回文串
                    dp[i][j] = false;
                }
            }
        }
        //遍历每一个字串，统计回文串个数
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (dp[i][j]) ans++;
            }
        }
        return ans;
    }
}
